Integrative Biomarker Discovery for Breast Cancer Metastasis from Gene Expression and Protein Interaction Data Using Error%2Dtolerant Pattern Mining.

A Comparative Study Of Algorithms For Land Cover Change.

A Knowledge Discovery Strategy for Relating Sea Surface Temperatures to Frequencies of Tropical Storms and Generating Predictions of Hurricanes Under 21st%2Dcentury Global Warming Scenarios.

Discovery of Patterns in Global Earth Science Data Using Data Mining.

Subspace Differential Coexpression Analysis Problem Definition and a General Approach.

Association Analysis Techniques for Bioinformatics Problems.
Abstract. Association analysis is one of the most popular analysis paradigms in data mining. Despite the solid foundation of association analysis and its potential applications, this group of techniques is not as widely used as classification and clustering, especially in the domain of bioinformatics and computational biology. In this paper, we present different types of association patterns and discuss some of their applications in bioinformatics. We present a case study showing the usefulness of association analysis-based techniques for pre-processing protein interaction networks for the task of protein function prediction. Finally, we discuss some of the challenges that need to be addressed to make association analysis-based techniques more applicable for a number of interesting problems in bioinformatics.
Using UML to Model EAE and Its Regulatory Network.

An association analysis approach to biclustering.
The discovery of biclusters, which denote groups of items that show coherent values across a subset of all the transactions in a data set, is an important type of analysis performed on real-valued data sets in various domains, such as biology. Several algorithms have been proposed to find different types of biclusters in such data sets. However, these algorithms are unable to search the space of all possible biclusters exhaustively. Pattern mining algorithms in association analysis also essentially produce biclusters as their result, since the patterns consist of items that are supported by a subset of all the transactions. However, a major limitation of the numerous techniques developed in association analysis is that they are only able to analyze data sets with binary and/or categorical variables, and their application to real-valued data sets often involves some lossy transformation such as discretization or binarization of the attributes. In
A Framework for Exploring Categorical Data.


Load Balancing for Parallel Optimization Techniques.


Incorporating functional inter%2Drelationships into protein function prediction algorithms.

Characterizing pattern preserving clustering.

Systematic Evaluation of Scaling Methods for Gene Expression Data.
Even after an experimentally prepared gene expression data set has been pre-processed to account for variations in the microarray technology, there may be inconsistencies between the scales of measurements in different conditions. This may happen for reasons such as the accumulation of gene expression data prepared by different laboratories into a single data set. A variety of scaling and transformation methods have been used for addressing these scale inconsistencies in different studies on the analysis of gene expression data sets. However, a quantitative estimation of their relative performance has been lacking. In this paper, we report an extensive evaluation of scaling and transformation methods for their effectiveness with respect to the important problem of protein function prediction. We consider several such commonly used methods for gene expression data, such as z-score scaling, quantile normalization, diff transformation, and two new scaling methods, sigmoid and double sigmoid, that have not been used previously in this domain to the best of our knowledge. We show that the performance of these methods can vary significantly across data sets, but Dsigmoid scaling and z-score transformation generally perform well for the two types of gene expression data, namely temporal and non-temporal, respectively. 1
Comparative Evaluation of Anomaly Detection Techniques for Sequence Data.
Anomaly detection has traditionally dealt with record or transaction type data sets. But in many real domains, data naturally occurs as sequences, and therefore the desire of studying anomaly detection techniques in sequential data sets. The problem of detecting anomalies in sequence data sets is related to but different from the traditional anomaly detection problem, because the nature of data and anomalies are different than those found in record data sets. While there are many surveys and comparative evaluations for traditional anomaly detection, similar studies are not done for sequence anomaly detection. We investigate a broad spectrum of anomaly detection techniques for symbolic sequences, proposed in diverse application domains. Our hypothesis is that symbolic sequences from different domains have distinct characteristics in terms of the nature of sequences as well as the nature of anomalies which makes it important to investigate how different techniques behave for different types of sequence data. Such a study is critical to understand the relative strengths and weaknesses of different techniques. Our paper is one such attempt where we have comparatively evaluated 7 anomaly detection techniques on 10 public data sets, collected from three diverse application domains. To gain further understanding in the performance of the techniques, we present a novel way to generate sequence data with desired characteristics. The results on the artificially generated data sets help us in experimentally verifying our hypothesis regarding different techniques. 
Quantitative evaluation of approximate frequent pattern mining algorithms.

Semi%2Dsupervised approach to rapid and reliable labeling of large data sets.

Semi%2Dsupervised approach to rapid and reliable labeling of large data sets.

Land cover change detection a case study.
The study of land cover change is an important problem in the Earth Science domain because of its impacts on local climate, radiation balance, biogeochemistry, hydrology, and the diversity and abundance of terrestrial species. Most well-known change detection techniques from statistics, signal processing and control theory are not well-suited for the massive high-dimensional spatio-temporal data sets from Earth Science due to limitations such as high computational complexity and the inability to take advantage of seasonality and spatio-temporal autocorrelation inherent in Earth Science data. In our work, we seek to address these challenges with new change detection techniques that are based on data mining approaches. Specifically, in this paper we have performed a case study for a new change detection technique for the land cover change detection problem. We study land cover change in the state of California, focusing on the San Francisco Bay Area and perform an extended study on the entire state. We also perform a comparative evaluation on forests in the entire state. These results demonstrate the utility of data mining techniques for the land cover change detection problem.
Similarity Measures for Categorical Data A Comparative Evaluation.
Measuring similarity or distance between two entities is a key step for several data mining and knowledge discovery tasks. The notion of similarity for continuous data is relatively well-understood, but for categorical data, the similarity computation is not straightforward. Several data-driven similarity measures have been proposed in the literature to compute the similarity between two categorical data instances but their relative performance has not been evaluated. In this paper we study the performance of a variety of similarity measures in the context of a specific data mining task: outlier detection. Results on a variety of data sets show that while no one measure dominates others for all types of problems, some measures are able to have consistently high performance. 1
Robust and efficient identification of biomarkers by classifying features on graphs.

Top 10 algorithms in data mining.
Abstract This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. These top 10 algorithms are among the most influential data mining algorithms in the research community. With each algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and review current and further research on the algorithm. These 10 algorithms cover classification,
Summary Report of SDM 2008 Panel Perspectives on Research Directions and Trends for the Data Mining Research Community.

Data Analysis in the 21st Century.

Summary Report of SDM 2008 Panel Perspectives on Research Directions and Trends for the Data Mining Research Community.

High Performance Data Mining %2D Application for Discovery of Patterns in the Global Climate System.

DDDAS%2FITR A Data Mining and Exploration Middleware for Grid and Distributed Computing.

Association analysis%2Dbased transformations for protein interaction networks a function prediction case study.
Protein interaction networks are one of the most promising types of biological data for the discovery of functional modules and the prediction of individual protein functions. However, it is known that these networks are both incomplete and inaccurate, i.e., they have spurious edges and lack biologically valid edges. One way to handle this problem is by transforming the original interaction graph into new graphs that remove spurious edges, add biologically valid ones, and assign reliability scores to the edges constituting the final network. We investigate currently existing methods, as well as propose a robust association analysis-based method for this task. This method is based on the concept of h-confidence, which is a measure that can be used to extract groups of objects having high similarity with each other. Experimental evaluation on several protein interaction data sets show that hyperclique-based transformations enhance the performance of standard function prediction algorithms significantly, and thus have merit. Categories and Subject Descriptors
Estimating False Negatives for Classification Problems with Cluster Structure.
Estimating the number of false negatives for a classifier when the true outcome of the classification is ascertained only for a limited number of instances is an important problem, with a wide range of applications from epidemiology to computer/network security. The frequently applied method is random sampling. However, when the target (positive) class of the classification is rare, which is often the case with network intrusions and diseases, this simple method results in excessive sampling. In this paper, we propose an approach that exploits the cluster structure of the data to significantly reduce the amount of sampling needed while guaranteeing an estimation accuracy specified by the user. The basic idea is to cluster the data and divide the clusters into a set of “strata”, such that the proportion of positive instances in the stratum is very low, very high or in between, respectively. By taking advantage of the different characteristics of the strata, more efficient estimation strategies can be applied, thereby significantly reducing the amount of required sampling. We also develop a computationally efficient clustering algorithm – referred to as class-focused partitioning – which uses the (imperfect) labels predicted by the classifier as additional guidance. We evaluated our method on the KDDCup network intrusion data set. Our method achieved better precision and accuracy with a 5 % sample than the best trial of simple random sampling with 40 % samples.
Generalizing the notion of confidence.
Abstract. Social aspects of security of information systems are often discussed in terms of “actual security ” and “perceived security”. This may lead to the hypothesis that e-voting is controversial because in paper voting, actual and perceived security coincide, whereas they do not in electronic systems. In this paper, we argue that the distinction between actual and perceived security is problematic from a philosophical perspective, and we develop an alternative approach, based on the notion of trust. We investigate the different meanings of this notion in computer science, and link these to the philosophical work of Luhmann, who distinguishes between familiarity, confidence and trust. This analysis yields several useful distinctions for discussing trust relations with respect to information technology. We apply our framework to electronic voting, and propose some hypotheses that can possibly explain the smooth introduction of electronic voting machines in the Netherlands in the early nineties. 1
Summarization %2D compressing data into an informative representation.
In this paper, we formulate the problem of summarization of a dataset of transactions with categorical attributes as an optimization problem involving two objective functions- compaction gain and information loss. We propose metrics to characterize the output of any summarization algorithm. We investigate two approaches to address this problem. The first approach is an adaptation of clustering and the second approach makes use of frequent itemsets from the association analysis domain. We illustrate one application of summarization in the field of network data where we show how our technique can be effectively used to summarize network traffic into a compact but meaningful representation. Specifically, we evaluate our proposed algorithms on the 1998 DARPA Off-line Intrusion Detection Evaluation data and network data generated by SKAION Corp for the ARDA information assurance program. 1
Computational Science and Its Applications %2D ICCSA 2006

Computational Science and Its Applications %2D ICCSA 2006

Computational Science and Its Applications %2D ICCSA 2006

Computational Science and Its Applications %2D ICCSA 2006

Computational Science and Its Applications %2D ICCSA 2006

Privacy Preserving Nearest Neighbor Search.

Divide and conquer approach for efficient pagerank computation.

Scan Detection A Data Mining Approach.
A precursor to many attacks on networks is often a reconnaissance operation, more commonly referred to as a scan. Despite the vast amount of attention focused on methods for scan detection, the state-ofthe-art methods suffer from high rate of false alarms and low rate of scan detection. In this paper, we formalize the problem of scan detection as a data mining problem. We show how the network traffic data sets can be converted into a data set that is appropriate for running off-the-shelf classifiers on. Our method successfully demonstrates that data mining models can encapsulate expert knowledge to create an adaptable algorithm that can substantially outperform state-ofthe-art methods for scan detection in both coverage and precision. 1
Hyperclique pattern discovery.
Abstract. Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of support. Also, it tends to generate too many spurious patterns involving items which are from different support levels and are poorly correlated. In this paper, we present a framework for mining highly-correlated association patterns called hyperclique patterns. In this framework, an objective measure called h-confidence is applied to discover hyperclique patterns. We prove that the objects in a hyperclique pattern have a guaranteed level of global pairwise similarity to one another as measured by the cosine similarity (uncentered Pearson’s correlation coefficient). Also, we show that the h-confidence measure satisfies a cross-support property which can help efficiently eliminate spurious patterns involving items with substantially different support levels. Indeed, this cross-support property is not limited to hconfidence and can be generalized to some other association measures. In addition, an algorithm called hyperclique miner is proposed to exploit both cross-support and anti-monotone properties of the h-confidence measure for the efficient discovery of hyperclique patterns. Finally, our experimental results show that hyperclique miner can efficiently identify hyperclique patterns, even at extremely low levels of support. Keywords: Association Analysis, Hyperclique Patterns, H-confidence 1.
Enhancing Data Analysis with Noise Removal.
Removing objects that are noise is an important goal of data cleaning as noise hinders most types of data  analysis. Most existing data cleaning methods focus on removing noise that is the result of low-level data errors  that result from an imperfect data collection process, but data objects that are irrelevant or only weakly relevant  can also significantly hinder data analysis. Thus, if the goal is to enhance the data analysis as much as possible,  these objects should also be considered as noise, at least with respect to the underlying analysis. Consequently,  there is a need for data cleaning techniques that remove both types of noise. Because data sets can contain large  amount of noise, these techniques also need to be able to discard a potentially large fraction of the data. This paper  explores four techniques intended for noise removal to enhance data analysis in the presence of high noise levels. Three of
TAPER A Two%2DStep Approach for All%2DStrong%2DPairs Correlation Query in Large Databases.
Abstract—Given a user-specified minimum correlation threshold and a market-basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold. However, when the number of items and transactions are large, the computation cost of this query can be very high. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson’s correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson’s correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A Two-step Allstrong-Pairs corElation queRy (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson’s correlation coefficient. Index Terms—Association analysis, data mining, Pearson’s correlation coefficient, statistical computing. 1
TAPER A Two%2DStep Approach for All%2DStrong%2DPairs Correlation Query in Large Databases.
Abstract—Given a user-specified minimum correlation threshold and a market-basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold. However, when the number of items and transactions are large, the computation cost of this query can be very high. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson’s correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson’s correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A Two-step Allstrong-Pairs corElation queRy (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson’s correlation coefficient. Index Terms—Association analysis, data mining, Pearson’s correlation coefficient, statistical computing. 1
Privacy leakage in multi%2Drelational databases a semi%2Dsupervised learning perspective.
In multi-relational databases, a view, which is a context- and content-dependent subset of one or more tables (or other views), is often used to preserve privacy by hiding sensitive information. However, recent developments in data mining present a new challenge for database security even when traditional database security techniques, such as database access control, are employed. This paper presents a data mining framework using semi-supervised learning that demonstrates the potential for privacy leakage in multi-relational databases. Many different types of semi-supervised learning techniques, such as the K-nearest neighbor (KNN) method, can be used to demonstrate privacy leakage. However, we also introduce a new approach to semi-supervised learning, hyperclique pattern based semi-supervised learning (HPSL), which differs from traditional semi-supervised learning approaches in that it considers the similarity among groups of objects instead of only pairs of objects. Our experimental results show that both the KNN and HPSL methods have the ability to compromise database security, although HPSL is better at this privacy violation (has higher prediction accuracy) than the KNN method. Finally, we provide a principle for avoiding privacy leakage in multi-relational databases via semi-supervised  learning and illustrate this principle with a simple preventive technique whose effectiveness is demonstrated by experiments.
Introduction to Data Mining
Introduction to Data Mining  We are in an age often referred to as the information age. In this information age, because we believe that information leads to power and success, and thanks to sophisticated technologies such as computers, satellites, etc., we have been collecting tremendous amounts of information. Initially, with the advent of computers and means for mass digital storage, we started collecting and storing all sorts of data, counting on the power of computers to help sort through this amalgam of information. Unfortunately, these massive collections of data stored on disparate structures very rapidly became overwhelming. This initial chaos has led to the creation of structured databases and database management systems (DBMS). The efficient database management systems have been very important assets for management of a large corpus of data and especially for effective and efficient retrieval of particular information from a large collection whenever needed. The prol
Computational Science and Its Applications %2D ICCSA 2005

Computational Science and Its Applications %2D ICCSA 2005


Computational Science and Its Applications %2D ICCSA 2005

Computational Science and Its Applications %2D ICCSA 2005


Generalizing the Notion of Confidence.
Abstract. Social aspects of security of information systems are often discussed in terms of “actual security ” and “perceived security”. This may lead to the hypothesis that e-voting is controversial because in paper voting, actual and perceived security coincide, whereas they do not in electronic systems. In this paper, we argue that the distinction between actual and perceived security is problematic from a philosophical perspective, and we develop an alternative approach, based on the notion of trust. We investigate the different meanings of this notion in computer science, and link these to the philosophical work of Luhmann, who distinguishes between familiarity, confidence and trust. This analysis yields several useful distinctions for discussing trust relations with respect to information technology. We apply our framework to electronic voting, and propose some hypotheses that can possibly explain the smooth introduction of electronic voting machines in the Netherlands in the early nineties. 1
Summarization %2D Compressing Data into an Informative Representation.
In this paper, we formulate the problem of summarization of a dataset of transactions with categorical attributes as an optimization problem involving two objective functions- compaction gain and information loss. We propose metrics to characterize the output of any summarization algorithm. We investigate two approaches to address this problem. The first approach is an adaptation of clustering and the second approach makes use of frequent itemsets from the association analysis domain. We illustrate one application of summarization in the field of network data where we show how our technique can be effectively used to summarize network traffic into a compact but meaningful representation. Specifically, we evaluate our proposed algorithms on the 1998 DARPA Off-line Intrusion Detection Evaluation data and network data generated by SKAION Corp for the ARDA information assurance program. 1
Feature bagging for outlier detection.
Outlier detection has recently become an important problem in many industrial and financial applications. In this paper, a novel feature bagging approach for detecting outliers in very large, high dimensional and noisy databases is proposed. It combines results from multiple outlier detection algorithms that are applied using different set of features. Every outlier detection algorithm uses a small subset of features that are randomly selected from the original feature set. As a result, each outlier detector identifies different outliers, and thus assigns to all data records outlier scores that correspond to their probability of being outliers. The outlier scores computed by the individual outlier detection algorithms are then combined in order to find the better quality outliers. Experiments performed on several synthetic and real life data sets show that the proposed methods for combining outputs from multiple outlier detection algorithms provide non-trivial improvements over the base algorithm.
Identification of Functional Modules in Protein Complexes via Hyperclique Pattern Discovery.

Incremental page rank computation on evolving graphs.
Link Analysis has been a popular and widely used Web mining technique, especially in the area of Web search. Various ranking schemes based on link analysis have been proposed, of which the PageRank metric has gained the most popularity with the success of Google. Over the last few years, there has been significant work in improving the relevance model of PageRank to address issues such as personalization and topic relevance. In addition, a variety of ideas have been proposed to address the computational aspects of PageRank, both in terms of efficient I/O computations and matrix computations involved in computing the PageRank score. The key challenge has been to perform computation on very large Web graphs. In this paper, we propose a method to incrementally compute PageRank for a large graph that is evolving. We note that although the Web graph evolves over time, its rate of change is rather slow. When compared to its size. We exploit the underlying principle of first order markov model on which PageRank is based, to incrementally compute PageRank for the evolving Web graph. Our experimental results show significant speed up in computational cost, the computation involves only the (small) portion of Web graph that has undergone change. Our approach is quite general, and can be used to incrementally compute (on evolving graphs) any metric that satisfies the first order Markov property.
Parallel and Distributed Computing for Cybersecurity.

IDR%2FQR An Incremental Dimension Reduction Algorithm via QR Decomposition.
Dimension reduction is critical for many database and data mining applications, such as e#cient storage and retrieval of high-dimensional data. In the literature, a well-known dimension reduction scheme is Linear Discriminant Analysis (LDA). The common aspect of previously proposed LDA based algorithms is the use of Singular Value Decomposition (SVD). Due to the di#culty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in LDA, there is little work on designing incremental LDA algorithms. In this paper, we propose an LDA based incremental dimension reduction algorithm, called IDR/QR, which applies QR Decomposition rather than SVD. Unlike other LDA based algorithms, this algorithm does not require the whole data matrix in main memory. This is desirable for large data sets. More importantly, with the insertion of new data items, the IDR/QR algorithm can constrain the computational cost by applying e#cient QR-updating techniques. Finally, we evaluate the e#ectiveness of the IDR/QR algorithm in terms of classification accuracy on the reduced dimensional space. Our experiments on several real-world data sets reveal that the accuracy achieved by the IDR/QR algorithm is very close to the best possible accuracy achieved by other LDA based algorithms. However, the IDR/QR algorithm has much less computational cost, especially when new data items are dynamically inserted.
Computational Science and Its Applications %2D ICCSA 2004
Despite the importance of proofs in assuring protocol implementers about the security properties of key establishment protocols, many protocol designers fail to provide any proof of security. Flaws detected long after the publication and/or implementation of protocols will erode the credibility of key establishment protocols. We revisit recent work of Choo, Boyd, Hitchcock, Maitland where they utilize the Bellare, Pointcheval, Rogaway (Authenticated key exchange secure against dictionary attacks, in: B. Preneel (Ed.), Advances in Cryptology – Eurocrypt 2000, Springer-Verlag, LNCS 1807/2000, pp. 139–155, 2000) computational complexity proof model in a machine specification and analysis (using an automated model checker – SHVT) for provably secure key establishment protocol analysis. We then examine several key establishment protocols without proofs of security, namely: protocols due to J.-K. Jan, Y.-H. Chen (A new
Computational Science and Its Applications %2D ICCSA 2004
Despite the importance of proofs in assuring protocol implementers about the security properties of key establishment protocols, many protocol designers fail to provide any proof of security. Flaws detected long after the publication and/or implementation of protocols will erode the credibility of key establishment protocols. We revisit recent work of Choo, Boyd, Hitchcock, Maitland where they utilize the Bellare, Pointcheval, Rogaway (Authenticated key exchange secure against dictionary attacks, in: B. Preneel (Ed.), Advances in Cryptology – Eurocrypt 2000, Springer-Verlag, LNCS 1807/2000, pp. 139–155, 2000) computational complexity proof model in a machine specification and analysis (using an automated model checker – SHVT) for provably secure key establishment protocol analysis. We then examine several key establishment protocols without proofs of security, namely: protocols due to J.-K. Jan, Y.-H. Chen (A new
Computational Science and Its Applications %2D ICCSA 2004
Despite the importance of proofs in assuring protocol implementers about the security properties of key establishment protocols, many protocol designers fail to provide any proof of security. Flaws detected long after the publication and/or implementation of protocols will erode the credibility of key establishment protocols. We revisit recent work of Choo, Boyd, Hitchcock, Maitland where they utilize the Bellare, Pointcheval, Rogaway (Authenticated key exchange secure against dictionary attacks, in: B. Preneel (Ed.), Advances in Cryptology – Eurocrypt 2000, Springer-Verlag, LNCS 1807/2000, pp. 139–155, 2000) computational complexity proof model in a machine specification and analysis (using an automated model checker – SHVT) for provably secure key establishment protocol analysis. We then examine several key establishment protocols without proofs of security, namely: protocols due to J.-K. Jan, Y.-H. Chen (A new
Computational Science and Its Applications %2D ICCSA 2004
Despite the importance of proofs in assuring protocol implementers about the security properties of key establishment protocols, many protocol designers fail to provide any proof of security. Flaws detected long after the publication and/or implementation of protocols will erode the credibility of key establishment protocols. We revisit recent work of Choo, Boyd, Hitchcock, Maitland where they utilize the Bellare, Pointcheval, Rogaway (Authenticated key exchange secure against dictionary attacks, in: B. Preneel (Ed.), Advances in Cryptology – Eurocrypt 2000, Springer-Verlag, LNCS 1807/2000, pp. 139–155, 2000) computational complexity proof model in a machine specification and analysis (using an automated model checker – SHVT) for provably secure key establishment protocol analysis. We then examine several key establishment protocols without proofs of security, namely: protocols due to J.-K. Jan, Y.-H. Chen (A new
Support envelopes a technique for exploring the structure of association patterns.
This paper introduces support envelopes—a new tool for analyzing association patterns—and illustrates some of their properties, applications, and possible extensions. Specifically, the support envelope for a transaction data set and a specified pair of positive integers (m, n) consists of the items and transactions that need to be searched to find any association pattern involving m or more transactions and n or more items. For any transaction data set with M transactions and N items, there is a unique lattice of at most M ∗ N support envelopes that captures the structure of the association patterns in that data set. Because support envelopes are not encumbered by a support threshold, this support lattice provides a complete view of the association structure of the data set, including association patterns that have low support. Furthermore, the boundary of the support lattice—the support boundary—has at most min(M, N) envelopes and is especially interesting since it bounds the maximum sizes of potential association patterns—not only for frequent, closed, and maximal itemsets, but also for patterns, such as error-tolerant itemsets, that are more general. The association structure can be represented graphically as a two-dimensional scatter plot of the (m, n) values associated with the support envelopes of the data set, a feature that is useful in the exploratory analysis of association patterns. Finally, the algorithm to compute support envelopes is simple and computationally efficient, and it is straightforward to parallelize the process of finding all the support envelopes.
Exploiting a support%2Dbased upper bound of Pearson%27s correlation coefficient for efficiently identifying strongly correlated pairs.
Given a user-specified minimum correlation threshold # and a market basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold #. However, when the number of items and transactions are large, the computation cost of this query can be very high. In this paper, we identify an upper bound of Pearson&#039;s correlation coe#cient for binary variables. This upper bound is not only much cheaper to compute than Pearson&#039;s correlation coe#cient but also exhibits a special monotone property which allows pruning of many item pairs even without computing their upper bounds. A Two-step All-strong-Pairs corrElation queRy (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent or improves when the number of items is increased in data sets with common Zipf or linear rank-support distributions. Experimental results from synthetic and real data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives.
IDR%2FQR an incremental dimension reduction algorithm via QR decomposition.
Dimension reduction is critical for many database and data mining applications, such as e#cient storage and retrieval of high-dimensional data. In the literature, a well-known dimension reduction scheme is Linear Discriminant Analysis (LDA). The common aspect of previously proposed LDA based algorithms is the use of Singular Value Decomposition (SVD). Due to the di#culty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in LDA, there is little work on designing incremental LDA algorithms. In this paper, we propose an LDA based incremental dimension reduction algorithm, called IDR/QR, which applies QR Decomposition rather than SVD. Unlike other LDA based algorithms, this algorithm does not require the whole data matrix in main memory. This is desirable for large data sets. More importantly, with the insertion of new data items, the IDR/QR algorithm can constrain the computational cost by applying e#cient QR-updating techniques. Finally, we evaluate the e#ectiveness of the IDR/QR algorithm in terms of classification accuracy on the reduced dimensional space. Our experiments on several real-world data sets reveal that the accuracy achieved by the IDR/QR algorithm is very close to the best possible accuracy achieved by other LDA based algorithms. However, the IDR/QR algorithm has much less computational cost, especially when new data items are dynamically inserted.
Generalizing the notion of support.
The goal of this paper is to show that generalizing the notion of support can be useful in extending association analysis to non-traditional types of patterns and non-binary data. To that end, we describe a framework for generalizing support that is based on the simple, but useful observation that support can be viewed as the composition of two functions: a function that evaluates the strength or presence of a pattern in each object (transaction) and a function that summarizes these evaluations with a single number. A key goal of any framework is to allow people to more easily express, explore, and communicate ideas, and hence, we illustrate how our support framework can be used to describe support for a variety of commonly used association patterns, such as frequent itemsets, general Boolean patterns, and error-tolerant itemsets. We also present two examples of the practical usefulness of generalized support. One example shows the usefulness of support functions for continuous data. Another example shows how the hyperclique pattern---an association pattern originally defined for binary data---can be extended to continuous data by generalizing a support function.
A Framework for Discovering Co%2DLocation Patterns in Data Sets with Extended Spatial Objects.

CREDOS Classification Using Ripple Down Structure %28A Case for Rare Classes%29.

HICAP Hierarchical Clustering with Pattern Preservation.

RBA An Integrated Framework for Regression based on Association Rules.

Selecting the right objective measure for association analysis.

Computational Science and Its Applications %2D ICCSA 2003

Computational Science and Its Applications %2D ICCSA 2003

Computational Science and Its Applications %2D ICCSA 2003

Optimizing F%2DMeasure with Support Vector Machines.

Optimizing F%2DMeasure with Support Vector Machines.

Localized Prediction of Continuous Target Variables Using Hierarchical Clustering.
In this paper, we propose a novel technique for the efficient prediction of multiple continuous target variables from high-dimensional and heterogeneous data sets using a hierarchical clustering approach. The proposed approach consists of three phases applied recursively: partitioning, localization and prediction. In the partitioning step, similar target variables are grouped together by a clustering algorithm. In the localization step, a classification model is used to predict which group of target variables is of particular interest. If the identified group of target variables still contains a large number of target variables, the partitioning and localization steps are repeated recursively and the identified group is further split into subgroups with more similar target variables. When the number of target variables per identified subgroup is sufficiently small, the third step predicts target variables using localized prediction models built from only those data records that correspond to the particular subgroup. Experiments performed on the problem of damage prediction in complex mechanical structures indicate that our proposed hierarchical approach is computationally more efficient and more accurate than straightforward methods of predicting each target variable individually or simultaneously using global prediction models. 1.
Mining Strong Affinity Association Patterns in Data Sets with Skewed Support Distribution.
Existing association-rule mining algorithms often rely on the support-based pruning strategy to prune its combinatorial search space. This strategy is not quite effective for data sets with skewed support distributions because they tend to generate many spurious patterns involving items from different support levels or miss potentially interesting low-support patterns. To overcome these problems, we propose the concept of hyperclique pattern, which uses an objective measure called h-confidence to identify strong affinity patterns. We also introduce the novel concept of crosssupport property for eliminating patterns involving items with substantially different support levels. Our experimental results demonstrate the effectiveness of this method for finding patterns in dense data sets even at very low support thresholds, where most of the existing algorithms would break down. Finally, hyperclique patterns also show great promise for clustering items in high dimensional space.
Discovery of climate indices using clustering.
To analyze the effect of the oceans and atmosphere on land climate, Earth Scientists have developed climate indices, which are time series that summarize the behavior of selected regions of the Earth’s oceans and atmosphere. In the past, Earth scientists have used observation and, more recently, eigenvalue analysis techniques, such as principal components analysis (PCA) and singular value decomposition (SVD), to discover climate indices. However, eigenvalue techniques are only useful for finding a few of the strongest signals. Furthermore, they impose a condition that all discovered signals must be orthogonal to each other, making it difficult to attach a physical interpretation to them. This paper presents an alternative clustering-based methodology for the discovery of climate indices that overcomes these limitations and is based on clusters that represent regions with relatively homogeneous behavior. The centroids of these clusters are time series that summarize the behavior of the ocean or atmosphere in those regions. Some of these centroids correspond to known climate indices and provide a validation of our methodology; other centroids are variants of known indices that may provide better predictive power for some land areas; and still other indices may represent potentially new Earth science phenomena. Finally, we show that cluster based indices generally outperform SVD derived indices, both in terms of area weighted correlation and direct correlation with the known indices.
Correlation Analysis of Spatial Time Series Datasets A Filter%2Dand%2DRefine Approach.
A spatial time series dataset is a collection of time series, each referencing a location in a common spatial framework. Correlation analysis is often used to identify pairs of interacting elements from the cross product of two spatial time series datasets. However, the computational cost of correlation analysis is very high when the dimension of the time series and the number of locations in the spatial frameworks are large. The key contribution of this paper is the use of spatial autocorrelation among spatial neighboring time series to reduce the computational cost. A filter-and-refine algorithm based on coning, i.e. grouping of locations, is proposed to reduce the cost of correlation analysis over a pair of spatial time series datasets. Cone-level correlation computation can be used to eliminate (filter out) a large number of element pairs whose correlation is clearly below (or above) a given threshold.
A New Clustering Algorithm for Transaction Data via Caucus.

A Comparative Study of Anomaly Detection Schemes in Network Intrusion Detection.
Abstract. Intrusion detection corresponds to a suite of techniques that can be used to identify attacks against computers and network infrastructures. Anomaly detection is a key element of intrusion detection systems in which perturbations of normal behavior suggest the presence of intentionally or unintentionally induced attacks, faults, defects, etc. Several recently developed anomaly and outlier detection schemes have been proposed for detecting novel attacks whose nature is unknown. To benefit the anomaly detection framework, a procedure for extracting additional useful features is also implemented. In addition, evaluation of anomaly detection algorithms is performed using standard metrics as well as specific metrics that are especially suitable in detecting intrusions that involve multiple network connections. The detailed comparison of anomaly detection algorithms applied to DARPA 1998 Intrusion Detection Evaluation Data demonstrate that depending on the attack type some anomaly detection schemes are more successful in detecting novel anomalies than others. However, during the past few months the most prominent techniques have also been applied to real network data, and they have been very successful in automatically identifying several novel intrusions, which were at the same time reported by CERT (Computer Emergency Response Team/Coordination Center) for additional investigation, since state-of-the-art intrusion detection techniques could not detect them. 1.
Finding Clusters of Different Sizes

Exploiting Spatial Autocorrelation to Efficiently Process Correlation%2DBased Similarity Queries.
A spatial time series dataset is a collection of time series, each referencing a location in a common spatial framework. Correlation analysis is often used to identify pairs of potentially interacting elements from the cross product of two spatial time series datasets (the two datasets may be the same). However, the computational cost of correlation analysis is very high when the dimension of the time series and the number of locations in the spatial frameworks are large. In this paper, we use a spatial autocorrelation-based search tree structure to propose new processing strategies for correlation based similarity range queries and similarity joins. We provide a preliminary evaluation of proposed strategies using algebraic cost models and experimental studies with Earth science datasets.
Usage Aware PageRank.
Web mining has been explored to a vast degree and different techniques have been proposed for a variety of applications that include Web Search, Web Classification, Web Personalization etc. Most research on Web mining has been from a ‘data-centric ’ point of view. The focus has been primarily on developing measures and applications based on data collected from content, structure and usage of Web till a particular time instance. In this project we examine another dimension of Web Mining, namely temporal dimension. Web data has been evolving over time, reflecting the ongoing trends. These changes in data in the temporal dimension reveal new kind of information. This information has not captured the attention of the Web mining research community to a large extent. In this paper, we highlight the significance of studying the evolving nature of the Web graphs. We have classified the approach to such problems at three levels of analysis: single node, sub-graphs and whole graphs. We provide a framework to approach problems of this kind and have identified interesting problems at each level. Our experiments verify the significance of such analysis and also point to future directions in this area. The approach we take is generic and can be applied to other domains, where data can be modeled as graph, such as network intrusion detection or social networks.
Finding Topics in Collections of Documents A Shared Nearest Neighbor Approach.
An important task in text mining is finding the dominant topics (and their associated documents) in a collection of documents. While traditional clustering techniques, e.g., hierarchical clustering and K-means, are often used for this task, this paper explores a new clustering algorithm which is based on a shared nearest neighbor approach. Unlike traditional clustering algorithms, not all the data is clustered, but instead, our algorithm discovers groups of documents representing strong topics and discards all documents that are not part of a strong topic. We  evaluate the performance of our algorithm on real and synthetic data sets and show that the groups of documents found by our technique often represent more coherent topics than those produced by K-means. Additionally, we provide a theoretical explanation for this behavior.
Predicting the Performance of Randomized Parallel Search An Application to Robot Motion Planning.

Proceedings of the Second SIAM International Conference on Data Mining

Applications on High Performance Computers.
The modeling and simulation efforts within Air Force Research Lab (AFRL) Sensors Directorate (SN) and Information Directorate (IF) have become increasingly complex. In order to develop, test, and analyze surveillance assets complex simulations and Matlab tools are developed to provide a better understanding of the environment. The increasing amount of primary and secondary data used to emulate the real world further increases the demands on systems used to simulate the environment. One option to overcome some of the computer resources needed to solve the problem is to leverage High Performance Computers (HPC). Within AFRL several approaches have been taken, we will focus on two; Matlab MPI and STAR-P. Both applications leverage Matlab and allow the user to have a familiar interface while expanding the computational limits of the users desktop and creating an environment that will run on a HPC. In the world of parallel computing the Message Passing Interface (MPI) is the de facto standard for implementing programs on multiple processors. MPI defines C, C++ and Fortran language functions for doing point-to-point communication in a parallel program. MatlabMPI is set of Matlab scripts that implement a subset of MPI and allow any Matlab program to be run on a parallel computer. STAR-P currently has a Matlab interface that combines all four parallel approaches in one environment: embarrassingly parallel, message passing, backend support and compilation. Where possible, STAR-P leverages established parallel numerical libraries to perform numerical computation. STAR-P integrates these wide ranges of linear algebra and other routines seamlessly with Matlab for the user. The end result gives the user a familiar interface, Matlab, and ability to use the HPC resources (CPU’s and Memory).
Selecting the right interestingness measure for association patterns.
Many techniques for association rule mining and feature selection require a suitable metric to capture the dependencies among variables in a data set. For example, metrics such as support, confidence, lift, correlation, and collective strength are often used to determine the interestinghess of association patterns. However, many such measures provide conflicting information about the interestinghess of a pattern, and the best metric to use for a given application domain is rarely known. In this paper, we present an overview of various measures proposed in the statistics, machine learning and data mining literature. We describe several key properties one should examine in order to select the right measure for a given application domain. A comparative study of these properties is made using twenty one of the existing measures. We show that each measure has different properties which make them useful for some application domains, but not for others. We also present two scenarios in which most of the existing measures agree with each other, namely, support-based pruning and table standardization. Finally, we present an algorithm to select a small set of tables such that an expert can select a desirable measure by looking at just this small set of tables.
Predicting Rare Classes Comparing Two%2DPhase Rule Induction to Cost%2DSensitive Boosting.

High Performance Data Mining.
Abstract. Recent times have seen an explosive growth in the availability of various kinds of data. It has resulted in an unprecedented opportunity to develop automated data-driven techniques of extracting useful knowledge. Data mining, an important step in this process of knowledge discovery, consists of methods that discover interesting, non-trivial, and useful patterns hidden in the data [SAD+93, CHY96]. The field of data mining builds upon the ideas from diverse fields such as machine learning, pattern recognition, statistics, database systems, and data visualization. But, techniques developed in these traditional disciplines are often unsuitable due to some unique characteristics of today’s data-sets, such as their enormous sizes, high-dimensionality, and heterogeneity. There is a necessity to develop effective parallel algorithms for various data mining techniques. However, designing such algorithms is challenging, and the main focus of the paper is a description of the parallel formulations of two important data mining algorithms: discovery of association rules, and induction of decision trees for classification. We also briefly discuss an application of data mining to the analysis of large data sets collected by Earth observing satellites that need to be processed to better understand global scale changes in biosphere processes and patterns. 1
Expert agreement and content based reranking in a meta search environment using Mearf.

Emerging scientific applications in data mining.
and store data, mine for new hypotheses, confirm with data or supplemental experiment.&#034; The long-term significance of the new data of molecular biology is that it can be combined with clinical medical data to achieve a higher-resolution understanding of the causes for and treatment of disease. A major challenge for data mining in biomedicine is therefore the organization of molecular data, cellular data, and clinical data in ways allowing them to be integrated for the sake of knowledge extraction.  A major additional source of information is the published medical literature, increasingly available online in full-text form or as useful (but unstructured) summaries of the main data and biomedical hypotheses.  Telecommunications  Data mining flourishes in telecommunications due to the availability of vast quantities of high-quality data. A significant stream of it consists of call records collected at network switches used primarily for EMERGING  SCIENTIFIC  APPLICATIONS IN DATA MINING  A
Parallel static and dynamic multi%2Dconstraint graph partitioning.

Discovery of Web Robot Sessions Based on their Navigational Patterns.
Web robots are software programs that automatically traverse the hyperlink structure of the World Wide Web in order to locate and retrieve information. There are many reasons why it is important to identify visits by the Web robots and distinguish them from other users. First of all, e-commerce retailers are particularly concerned about the unauthorized deployment of robots for gathering business intelligence at their Web sites. In addition, Web robots tend to consume considerable network bandwidth at the expense of other users. Sessions due to Web robots also make it more difficult to perform clickstream analysis effectively on the Web data. Conventional techniques for detecting Web robots are often based on identifying the IP address and user agent of the Web clients. While these techniques are applicable to many well-known robots, they may not be sufficient to detect camouaging and previously unknown robots. In this paper, we propose an alternative approach that uses the navigational patterns in the click-stream data to determine if it is due to a robot. Experimental results on our Computer Science department Web server logs show that highly accurate classification models can be built using this approach. We also show that these models are able to discover many camouflaging and previously unidentified robots.
Graph Partitioning for Dynamic%2C Adaptive and Multi%2Dphase Scientific Simulations.
The efficient execution of scientific simulations on HPC systems requires a partitioning of the underlying mesh among the processors such that the load is balanced and the inter-processor communication is minimized. Graph partitioning algorithms have been applied with much success for this purpose. However, the parallelization of multi-phase and multi-physics computations poses new challenges that require fundamental advances in graph partitioning technology. In addition, most existing graph partitioning algorithms are not suited for the newer heterogeneous highperformance computing platforms. This talk will describe research efforts in our group that are focused on developing novel multi-constraint and multi-objective graph partitioning algorithms that can support the advancing state-ofthe-art in numerical simulation technologies. In addition, we will present our preliminary work on new partitioning algorithms that are well suited for heterogeneous architectures. 1.
Evaluating Boosting Algorithms to Classify Rare Classes Comparison and Improvements.
Classification of rare events has many important data mining applications. Boosting is a promising metatechnique that improves the classification performance of any weak classifier. So far, no systematic study has been conducted to evaluate how boosting performs for the task of mining rare classes. In this paper, we evaluate three existing categories of boosting algorithms from the single viewpoint of how they update the example weights in each iteration, and discuss their possible effect on recall and precision of the rare class. We propose enhanced algorithms in two of the categories, and justify their choice of weight updating parameters theoretically. Using some specially designed synthetic datasets, we compare the capability of all the algorithms from the rare class perspective. The results support our qualitative analysis, and also indicate that our enhancements bring an extra capability for achieving better balance between recall and precision in mining rare classes.
Architecture Independent Analysis of Parallel Programs.

Text Categorization Using Weight Adjusted k%2DNearest Neighbor Classification.
Categorization of documents is challenging, as the number of discriminating words can be very large. We present a nearest neighbor classification scheme for text categorization in which the importance of discriminating words is learned using mutual information and weight adjustment techniques. The nearest neighbors for a particular document are then computed based on the matching words and their weights. We evaluate our scheme on both synthetic and real world documents. Our experiments with synthetic data sets show that this scheme is robust under different emulated conditions. Empirical results on real world documents demonstrate that this scheme outperforms state of the art classification algorithms such as C4.5, RIPPER, Rainbow, and PEBLS.
Mining Needle in a Haystack Classifying Rare Classes via Two%2Dphase Rule Induction.
Learning models to classify rarely occurring target classes is an important problem with applications in network intrusion detection, fraud detection, or deviation detection in general. In this paper, we analyze our previously proposed two-phase rule induction method in the context of learning complete and precise signatures of rare classes. The key feature of our method is that it separately conquers the objectives of achieving high recall and high precision for the given target class. The first phase of the method aims for high recall by inducing rules with high support and a reasonable level of accuracy. The second phase then tries to improve the precision by learning rules to remove false positives in the collection of the records covered by the first phase rules. Existing sequential covering techniques try to achieve high precision for each individual disjunct learned. In this paper, we claim that such approach is inadequate for rare classes, because of two problems: splintered false positives and error-prone small disjuncts. Motivated by the strengths of our two-phase design, we design various synthetic data models to identify and analyze the situations in which two state-of-the-art methods, RIPPER and C4.5rules, either fail to learn a model or learn a very poor model. In all these situations, our two-phase approach learns a model with significantly better recall and precision levels. We also present a comparison of the three methods on a challenging real-life network intrusion detection dataset. Our method is significantly better or comparable to the best competitor in terms of achieving better balance between recall and precision.  1. 
Mining Indirect Associations in Web Data.

Wavefront Diffusion and LMSR Algorithms for Dynamic Repartitioning of Adaptive Meshes.
Existing state-of-the-art schemes for dynamic repartitioning of adaptive meshes can be classified as either diffusion-based schemes or scratch-remap schemes. We present a new scratch-remap scheme called Locally-Matched Multilevel Scratch-Remap (or simply LMSR). The LMSR scheme tries to compute a partitioning that has a high overlap with the existing partitioning. We show that LMSR decreases the amount of vertex migration required to balance the graph compared to current scratch-remap schemes, particularly for slightly imbalanced graphs. We describe a new diffusion-based scheme that we refer to as Wavefront Diffusion. In Wavefront Diffusion, the flow of vertices moves in a wavefront from overweight to underweight domains. We show that Wavefront Diffusion obtains significantly lower vertex migration requirements while maintaining similar or better edge-cut results compared to existing diffusion algorithms, especially for highly imbalanced graphs. Furthermore, we compare Wavefront Diffusi...
Guest Editors%27 Introduction Special Issue on High%2DPerformance Data Mining.

Memory Management Techniques for Gang Scheduling.

Parallel Multilevel Algorithms for Multi%2Dconstraint Graph Partitioning %28Distinguished Paper%29.

Load Balancing Across Near%2DHomogeneous Multi%2DResource Servers.
An emerging model for computational grids interconnects similar multi-resource servers from distributed sites. A job submitted to the grid can be executed by any of the servers; however, resource size or balance may be different across servers. One approach to resource management for this grid is to layer a global load distribution system on top of the local job management systems at each site. Unfortunately, classical load distribution policies fail on two aspects when applied to a multi-resource server grid. First, simple load indices may not recognize that a resource imbalance exists at a server. Second, classical job selection policies do not actively correct such a resource imbalanced state. We show through simulation that new policies based on resource balancing perform consistently better than the classical load distribution strategies. 1.
Graph Partitioning for Dynamic%2C Adaptive%2C and Multi%2Dphase Computations.

Distributed and parallel knowledge discovery %28workshop session %2D title only%29.

Indirect Association Mining Higher Order Dependencies in Data.
This paper introduces a novel pattern called indirect association and examines its utility in various application domains. Existing algorithms for mining associations, such as Apriori, will only discover itemsets that have support above a user-defined threshold. Any itemsets with support below the minimum support requirement are filtered out. We believe
A Unified Algorithm for Load%2Dbalancing Adaptive Scientific Simulations.

Scalable Parallel Data Mining for Association Rules.
One of the important problems in data mining is discovering association rules from databases of transactions where each transaction consists of a set of items. The most time consuming operation in this discovery process is the computation of the frequency of the occurrences of interesting subset of items (called candidates) in the database of transactions. To prune the exponentially large space of candidates, most existing algorithms, consider only those candidates that have a user defined minimum support. Even with the pruning, the task of finding all association rules requires a lot of computation power and time. Parallel computers offer a potential solution to the computation requirement of this task, provided efficient and scalable parallel algorithms can be designed. In this paper, we present two new parallel algorithms for mining association rules. The Intelligent Data Distribution algorithm efficiently uses aggregate memory of the parallel computer by employing intelligent candi...
Report from the Workshop on Distributed and Parallel Knowledge Discovery


Multilevel k%2Dway Hypergraph Partitioning.
In this paper, we present a new multilevel k-way hypergraph partitioning algorithm that substantially outperforms the existing state-of-the-art K-PM/LR algorithm for multi-way partitioning. both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those produced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the (K  -  1) metric. Furthermore, our algorithm is significantly faster, requiring 4 to 5 times less time than that required by K-PM/LR. 1 Introduction  Hypergraph partitioning is an important problem with extensive application to many areas, including VLSI design [10], efficient storage of large databases on disks [14], and data mining [13]. The problem is to partition the vertices of a hypergraph into k roughly equal parts, such that a certain objective function defined over the hyperedges is optimized. A commonly used obje...

High Performance Data Mining.
Abstract. Recent times have seen an explosive growth in the availability of various kinds of data. It has resulted in an unprecedented opportunity to develop automated data-driven techniques of extracting useful knowledge. Data mining, an important step in this process of knowledge discovery, consists of methods that discover interesting, non-trivial, and useful patterns hidden in the data [SAD+93, CHY96]. The field of data mining builds upon the ideas from diverse fields such as machine learning, pattern recognition, statistics, database systems, and data visualization. But, techniques developed in these traditional disciplines are often unsuitable due to some unique characteristics of today’s data-sets, such as their enormous sizes, high-dimensionality, and heterogeneity. There is a necessity to develop effective parallel algorithms for various data mining techniques. However, designing such algorithms is challenging, and the main focus of the paper is a description of the parallel formulations of two important data mining algorithms: discovery of association rules, and induction of decision trees for classification. We also briefly discuss an application of data mining to the analysis of large data sets collected by Earth observing satellites that need to be processed to better understand global scale changes in biosphere processes and patterns. 1
Efficient Parallel Algorithms for Mining Associations.

Dynamic Repartitioning of Adaptively Refined Meshes.

PSPASES An Efficient and Scalable Parallel Sparse Direct Solver.
Many problems in engineering and scientific domains require solving large sparse systems of linear equations, as a computationally intensivesteptowards the final solution. It has long beenachallenge to develop efficient parallel formulations of sparse direct solvers due to several different complex steps involved in the process. In this paper, we describe PSPASES, one of the first efficient, portable, and robust scalable parallel solvers for sparse symmetric positive definite linear systems that wehavedeveloped. We discuss the algorithmic and implementation issues involved in its development# and present performance and scalability results on CrayT3E and SGI Origin 2000. PSPASES could solve the largest sparse system (1 million equations) ever solved by a direct method, with the highest performance (51 GFLOPS for Cholesky factorization) ever reported. 
Document Categorization and Query Generation on the World Wide Web Using WebACE.
We present WebACE, an agent for exploring and categorizing documents on the World Wide Web based on a user profile. The heart of the agent is an unsupervised categorization of a set of documents, combined with a process for generating new queries that is used to search for new related documents and for filtering the resulting documents to extract the ones most closely related to the starting set. The document categories are not given a priori. We present the overall architecture and describe two novel algorithms which provide significant improvement over traditional clustering algorithms and form the basis for the query generation and search component of the agent. We report on the results of our experiments comparing these new algorithms with more traditional clustering algorithms and we show that our algorithms are fast and scalable.
Parallel Formulations of Decision%2DTree Classification Algorithms.
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target  marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable  for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees  have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. In  this paper, we present parallel formulations of classification decision tree learning algorithm based on induction. We  describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other  is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these  methods and propose a hybrid method that employs the good features of these methods. We also provide the analysis  of the cost of computation and communication of the proposed hybr...
Chameleon Hierarchical Clustering Using Dynamic Modeling.
Many advanced algorithms have difficulty dealing with highly variable clusters that do not follow a preconceived model. By basing its selections on both interconnectivity and closeness, the Chameleon algorithm yields accurate results for these highly variable clusters.
WSSMP A High%2DPerformance Serial and Parallel Symmetric Sparse Linear Solver.

State of the Art in Parallel Search Techniques for Discrete Optimization Problems.

Multilevel hypergraph partitioning applications in VLSI domain.
In this paper, we present a new hypergraphpartitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%–23 % better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4–10 times less time than that required by the other schemes. Our multilevel hypergraph-partitioning algorithm scales very well for large hypergraphs. Hypergraphs with over 100 000 vertices can be bisected in a few minutes on today’s workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9%–30%).  
WebACE A Web Agent for Document Categorization and Exploration.
We propose an agent for exploring and categorizing documents on the World Wide Web. The heart of the agent is an automatic categorization of a set of documents, combined with a process for generating new queries used to search for new related documents and filtering the resulting documents to extract the set of documents most closely related to the starting set. The document categories are not given a-priori. We present the overall architecture and describe two novel algorithms which provide significant improvement over traditional clustering algorithms and form the basis for the query generation and search component of the agent.  1 Introduction  The World Wide Web is a vast resource of information and services that continues to grow rapidly. Powerful search engines have been developed to aid in locating unfamiliar documents by category, contents, or subject. Relying on large indexes to documents located on the Web, search engines determine the URLs of those documents satisfying a use...
Parallel Formulations of Decision%2DTree Classification Algorithms.
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target  marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable  for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees  have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. In  this paper, we present parallel formulations of classification decision tree learning algorithm based on induction. We  describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other  is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these  methods and propose a hybrid method that employs the good features of these methods. We also provide the analysis  of the cost of computation and communication of the proposed hybr...
ScalParC A New Scalable and Efficient Parallel Classification Algorithm for Mining Large Datasets.
In this paper, we present ScalParC (Scalable Parallel Classifier), a new parallel formulation of a decision tree based classification process. Like other state-of-the-art decision tree classifiers such as SPRINT, ScalParC is suited for handling large datasets. We show that existing parallel formulation of SPRINT is unscalable, whereas ScalParC is shown to be scalable in both runtime and memory requirements. We present the experimental results of classifying up to 6.4 million records on up to 128 processors of Cray T3D, in order to demonstrate the scalable behavior of ScalParC. A key component of ScalParC is the parallel hash table. The proposed parallel hashing paradigm can be used to parallelize other algorithms that require many concurrent updates to a large hash table.  1 Introduction  Classification is an important problem in the rapidly emerging field of data mining. The problem can be stated as follows. We are given a training dataset consisting of records. Each record is identif...
WSSMP A High%2DPerformance Serial and Parallel Symmetric Sparse Linear Solver.

Load Balancing of Dynamic and Adaptive Mesh%2DBased Computations.

Hypergraph Based Clustering in High%2DDimensional Data Sets A Summary of Results.
Clustering of data in a large dimension space is of a great interest in many data mining applications. In this paper, we propose a method for clustering of data in a high dimensional space based on a hypergraph model. In this method, the relationship present in the original data in high dimensional space are mapped into a hypergraph. A hyperedge represents a relationship (affinity) among subsets of data and the weight of the hyperedge reflects the strength of this affinity. A hypergraph partitioning algorithm is used to find a partitioning of the vertices such that the corresponding data items in each partition are highly related and the weight of the hyperedges cut by the partitioning is minimized. We present results of experiments on two different data sets: S&amp;P500 stock data for the period of 1994-1996 and protein coding data. These experiments demonstrate that our approach is applicable and effective in high dimensional datasets. 1 Introduction  Clustering in data mining is a disco...
Declustering and Load%2DBalancing Methods for Parallelizing Geographic Information Systems.
Declustering and load-balancing are important issues in designing a high performance geographic information system (HPGIS) which is a central component of many interactive applications such as real-time terrain visualization. The current literature provides efficient methods for declustering spatial point-data. However, there has been little work towards developing efficient declustering methods for collections of extended objects like chains of line-segments and polygons. In this paper, we focus on the data-partitioning approach to parallelizing GIS operations. We provide a framework for declustering collections of extended spatial objects by identifying the following key issues: (i) the work-load metric, (ii) the spatial-extent of the work-load, (iii)the distribution of the work-load over the spatial-extent, and (iv) the declustering method. We identify and experimentally evaluate alternatives for each of these issues. In addition, we also provide a framework for dynamicall...
A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering.

Multilevel k%2Dway Partitioning Scheme for Irregular Graphs.

Scalable Parallel Formulations of the Barnes%2DHut Method for n%2DBody Simulations.
In this paper, we present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.   
Multilevel Hypergraph Partitioning Application in VLSI Domain.
In this paper, we present a new hypergraphpartitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%–23 % better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4–10 times less time than that required by the other schemes. Our multilevel hypergraph-partitioning algorithm scales very well for large hypergraphs. Hypergraphs with over 100 000 vertices can be bisected in a few minutes on today’s workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9%–30%).  
Clustering Based On Association Rule Hypergraphs.
Clustering in data mining is a discovery process that groups a set of data such that the intracluster similarity is maximized and the intercluster similarity is minimized. These discovered clusters are used to explain the characteristics of the data distribution. In this paper we propose a new methodology for clustering related items using association rules, and clustering related transactions using clusters of items. Our approach is linearly scalable with respect to the number of transactions. The frequent item-sets used to derive association rules are also used to group items into a hypergraph edge, and a hypergraph partitioning algorithm is used to find the clusters. Our experiments indicate that clustering using association rule hypergraphs holds great promise in several application domains. Our experiments with stock-market data and congressional voting data show that this clustering scheme is able to successfully group items that belong to the same group. Clustering of items can ...
Repartitioning of Adaptive Meshes Experiments with Multilevel Diffusion.

A Coarse%2DGrain Parallel Formulation of Multilevel k%2Dway Graph Partitioning Algorithm.
In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm, that is particularly suited for message-passing libraries that have high latency. The multilevel k-way partitioning algorithm reduces the size of the graph by successively collapsing vertices and edges (coarsening phase), finds a k-way partitioning of the smaller graph, and then it constructs a k-way partitioning for the original graph by projecting and refining the partition to successively finer graphs (uncoarsening phase). Our algorithm is able to achieve a high degree of concurrency, while maintaining the high quality partitions produced by the serial algorithm.  
Design and Implementation of a Scalable Parallel Direct Solver for Sparse Symmetric Positive Definite Systems Preliminary Results.
Solving large sparse systems of linear equations is at the core of many problems in engineering and scientific computing. It has long been a challenge to develop parallel formulations of sparse direct solvers due to several different complex steps involved in the process. In this paper, we describe one of the first efficient, practical, and robust parallel solvers for sparse symmetric positive definite linear systems that we have developed and discuss the algorithmic and implementation issues involved in its development. 1 Introduction  Solving large sparse systems of linear equations is at the heart of many engineering and scientific computing applications. There are two methods to solve these systems - direct and iterative. Direct methods are preferred for many applications because of various properties of the method and the nature of the application. A wide class of sparse linear systems arising in practice have a symmetric positive definite (SPD) coefficient matrix. The problem is ...
Role of Message%2DPassing in Performance Oriented Parallel Programming.

Scalable Parallel Data Mining for Association Rules.
One of the important problems in data mining is discovering association rules from databases of transactions where each transaction consists of a set of items. The most time consuming operation in this discovery process is the computation of the frequency of the occurrences of interesting subset of items (called candidates) in the database of transactions. To prune the exponentially large space of candidates, most existing algorithms, consider only those candidates that have a user defined minimum support. Even with the pruning, the task of finding all association rules requires a lot of computation power and time. Parallel computers offer a potential solution to the computation requirement of this task, provided efficient and scalable parallel algorithms can be designed. In this paper, we present two new parallel algorithms for mining association rules. The Intelligent Data Distribution algorithm efficiently uses aggregate memory of the parallel computer by employing intelligent candi...
Highly Scalable Parallel Algorithms for Sparse Matrix Factorization.
In this paper, we describe a scalable parallel algorithm for sparse matrix factorization, analyze their performance and scalability, and present experimental results for up to 1024 processors on a Cray T3D parallel computer. Through our analysis and experimental results, we demonstrate that our algorithm substantially improves the state of the art in parallel direct solution of sparse linear systems—both in terms of scalability and overall performance. It is a well known fact that dense matrix factorization scales well and can be implemented efficiently on parallel computers. In this paper, we present the first algorithm to factor a wide class of sparse matrices (including those arising from two- and three-dimensional finite element problems) that is asymptotically as scalable as dense matrix factorization algorithms on a variety of parallel architectures. Our algorithm incurs less communication overhead and is more scalable than any previously known parallel formulation of sparse matrix factorization. Although, in this paper, we discuss Cholesky factorization of symmetric positive definite matrices, the algorithms can be adapted for solving sparse linear least squares problems and for Gaussian elimination of diagonally dominant matrices that are almost symmetric in structure. An implementation of our sparse Cholesky factorization algorithm delivers up to 20 GFlops on a Cray T3D for medium-size structural engineering and linear programming problems. To the best of our knowledge,
Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes.
For a large class of irregular mesh applications, the structure of the mesh changes from one phase of the computation  to the next. Eventually, as the mesh evolves, the adapted mesh has to be repartitioned to ensure good load  balance. If this new graph is partitioned from scratch, it may lead to an excessive migration of data among processors.  In this paper, we present schemes for computing repartitionings of adaptively refined meshes that perform diffusion of   
A parallel Formulation of Informed Randomized Search for Robot Motion Planning Problems.
We show how paths for articulated robots with many degrees of freedom can be generated in a few seconds or less using nonsystematic parallel search. We present experimental results obtained on a multicomputer for an accurate model of a 7-jointed manipulator arm operating in realistic 3D workspaces. We then present and discuss a fast method for smoothing the paths delivered by the parallel algorithm.  1 Introduction  Among the many skills robots require is the ability to plan the paths they must take while executing their tasks. The intent of this paper is to provide experimental evidence that very fast path planning can be performed using parallel algorithms. By very fast we mean systems that produce solutions in fractions of seconds or a few seconds for complex environments and robots with over four degrees of freedom (dof).  We have developed a parallel formulation of the Randomized Path Planner proposed by Barraquand and Latombe [2]. Our parallel formulation has proved extremely eff...
Parallel Multilevel Graph Partitioning.

Parallelizing a GIS on a Shared Address Space Architecture.

Multilevel Graph Partitioning Schemes.
Abstract – In this paper we present experiments with a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a new scheme for refining during uncoarsening that is much faster than the Kernighan-Lin refinement. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme consistently produces partitions that are better than those produced by spectral partitioning schemes in substantially smaller timer (10 to 35 times faster than multilevel spectral bisection). Also, when our scheme is used to compute fill reducing orderings for sparse matrices, it substantially outperforms the widely used multiple minimum degree algorithm. 1
A parallel Formulation of Informed Randomized Search for Robot Motion Planning Problems.
We show how paths for articulated robots with many degrees of freedom can be generated in a few seconds or less using nonsystematic parallel search. We present experimental results obtained on a multicomputer for an accurate model of a 7-jointed manipulator arm operating in realistic 3D workspaces. We then present and discuss a fast method for smoothing the paths delivered by the parallel algorithm.  1 Introduction  Among the many skills robots require is the ability to plan the paths they must take while executing their tasks. The intent of this paper is to provide experimental evidence that very fast path planning can be performed using parallel algorithms. By very fast we mean systems that produce solutions in fractions of seconds or a few seconds for complex environments and robots with over four degrees of freedom (dof).  We have developed a parallel formulation of the Randomized Path Planner proposed by Barraquand and Latombe [2]. Our parallel formulation has proved extremely eff...
A Highly Parallel Interior Point Algorithm.

N%2DBody Simulations Using Message Passsing Parallel Computers.

Optimally Scalable Parallel Sparse Cholesky Factorization.

Position Paper.
This position paper describes experience with a repository-based framework for evolutionary software development, designed, developed and used at Argo to support its administration. Argo is a semi-government organization managing several hundred public schools. It uses this framework to develop its applications, which share a common business model, and require database, electronic document, workflow and Internet functionality. The framework uses a (meta-)repository to capture formal and informal knowledge of the business model. Part of this knowledge is explicitly modeled; other practices are less formally specified. To model, configure and manage the repository, we provide the user with several high-level tools that require only the business model to get the system up and running. With the end-user tools, users select applications, enter and view data, query the repository, display, print and export the results of a query, access the thesaurus and manage electronic documents, workflow...
Analysis of Multilevel Graph Partitioning.
Recently, a number of researchers have investigated a class of algorithms that are based on multilevel graph partitioning that have moderate computational complexity, and provide excellent graph partitions. However, there exists little theoretical analysis that could explain the ability of multilevel algorithms to produce good partitions. In this paper we present such an analysis. We show under certain reasonable assumptions that even if no refinement is used in the uncoarsening phase, a good bisection of the coarser graph is worse than a good bisection of the finer graph by at most a small factor. We also show that the size of a good vertex-separator of the coarse graph projected to the finer graph (without performing refinement in the uncoarsening phase) is higher than the size of a good vertexseparator of the finer graph by at most a small factor.
Parallel Algorithms for Forward and Back Substitution in Direct Solution of Sparse Linear Systems.
A few parallel algorithms for solving triangular systems  resulting from parallel factorization of sparse linear systems  have been proposed and implemented recently. We  present a detailed analysis of parallel complexity and scalability  of the best of these algorithms and the results of  its implementation on up to 256 processors of the Cray  T3D parallel computer. It has been a common belief that  parallel sparse triangular solvers are quite unscalable due  to a high communication to computation ratio. Our analysis  and experiments show that, although not as scalable  as the best parallel sparse Cholesky factorization algorithms,  parallel sparse triangular solvers can yield reasonable  speedups in runtime on hundreds of processors. We  also show that for a wide class of problems, the sparse triangular  solvers described in this paper are optimal and are  asymptotically as scalable as a dense triangular solver.
Parallel Matrix%2DVector Product Using Approximate Hierarchical Methods.
Matrix-vector products (mat-vecs) form the core of iterative methods used for solving dense linear systems. Often, these systems arise in the solution of integral equations used in electromagnetics, heat transfer, and wave propagation. In this paper, we present a parallel approximate method for computing mat-vecs used in the solution of integral equations. We use this method to compute dense mat-vecs of hundreds of thousands of elements. The combined speedups obtained from the use of approximate methods and parallel processing represent an improvement of several orders of magnitude over exact mat-vecs on uniprocessors. We demonstrate that our parallel formulation incurs minimal parallel processing overhead and scales up to a large number of processors. We study the impact of varying the accuracy of the approximate mat-vec on overall time and on parallel efficiency.    This work was supported by IST/BMDO through Army Research Office contract DA/DAAH04-93-G-0080, NSF grant NSG/1RI-921694...
Load Balancing in High Performance GIS Declustering Polygonal Maps.

Performance and Scalability of Preconditioned Conjugate Gradient Methods on Parallel Computers.

Parallel Search Algorithms for Discrete Optimization Problems.

Introduction to Parallel Computing.

A Parallel Parsing Algorithm for Natural Language using Tree Adjoining Grammar.
Dee Adjoining Grammar (TAG) is a powerful grammatical formalism for large-scale natural lan-guage processing. However, the computational com-plexity of parsing algorithms for TAG is high. We introduce a new parallel TAG parsing algorithm for MIMD hypercube multicomputers, using large-granularity grammar partitioning, asynchronous com-munication, and distributed termination detection. We describe our implementation on the nCUBE/2 parallel computer, and provide experimental resulis on both random and English grammars. Our algo-rithm delivers the best performance of any TAG pars-ing algorithm to date, yielding an almost two order-of-magnitude speedup and good eficiency on up to 256 processors. TAG parsing is a highly unstructured problem. Based on our experience developing a parallel TAG parser, we draw some general conclusions for solving other unstructured problems.
A parallel formulation of interior point algorithms.

Scalable parallel formulations of the Barnes%2DHut method for n%2Dbody simulations.
In this paper, we present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.   
A scalable parallel algorithm for sparse Cholesky factorization.
In this paper, we describe a scalable parallel algorithm for sparse Cholesky factorization, analyze its performance and scalability, and present experimental results of its implementation on a 1024-processor nCUBE2 parallel computer. Through our analysis and experimental results, we demonstrate that our algorithm improves the state of the art in parallel direct solution of sparse linear systems by an order of magnitude---both in terms of speedups and the number of processors that can be utilized effectively for a given problem size. This algorithm incurs strictly less communication overhead and is more scalable than any known parallel formulation of sparse matrix factorization. We show that our algorithm is optimally scalable on hypercube and mesh architectures and that its asymptotic scalability is the same as that of dense matrix factorization for a wide class of sparse linear systems, including those arising in all two- and three- dimensional finite element problems. 1 Introduction ...
Unstructured Tree Search on SIMD Parallel Computers.
In this paper, we present new methods for load balancing of unstructured tree computations on large-scale SIMD machines, and analyze the scalability of these and other existing schemes. An efficient formulation of tree search on a SIMD machine comprises of two major components: (i) a triggering mechanism, which determines when the search space redistribution must occur to balance search space over processors; and (ii) a scheme to redistribute the search space. We have devised a new redistribution mechanism and a new triggering mechanism. Either of these can be used in conjunction with triggering and redistribution mechanisms developed by other researchers. We analyze the scalability of these mechanisms, and verify the results experimentally. The analysis and experiments show that our new load balancing methods are highly scalable on SIMD architectures. Their scalability is shown to be no worse than that of the best load balancing schemes on MIMD architectures. We verify our theoretical...
A Scalable Parallel Formulation of the Backpropagation Algorithm for Hypercubes and Related Architectures.
Abstract In this paper, we present a new technique for mapping the backpropagation algorithm on hypercubes and related architectures. A key component of this technique is a network partitioning scheme which is called checkerboarding. Checkerboarding allows us to replace the all-to-all broadcast operation performed by the commonly used vertical network partitioning scheme, with operations that are much faster on the hypercubes and related architectures. Checkerboarding can be combined with the pattern partitioning technique to form a hybrid scheme which performs better than either one of these schemes. Theoretical analysis and experimental results on nCUBE2TM y and CM5TM z show that our scheme performs better than the other schemes, both for uniform and non-uniform networks.
Scalable Load Balancing Techniques for Parallel Computers.
In this paper we analyze the scalability of a number of load balancing algorithms which can  be applied to problems that have the following characteristics : the work done by a processor  can be partitioned into independent work pieces; the work pieces are of highly variable sizes;  and it is not possible (or very difficult) to estimate the size of total work at a given processor.  Such problems require a load balancing scheme that distributes the work dynamically among  different processors.  Our goal here is to determine the most scalable load balancing schemes for different architectures  such as hypercube, mesh and network of workstations. For each of these architectures,  we establish lower bounds on the scalability of any possible load balancing scheme. We present  the scalability analysis of a number of load balancing schemes that have not been analyzed  before. This gives us valuable insights into their relative performance for different problem and  architectural characteristi...
Scalability of Parallel Algorithms for Matrix Multiplication.
A number of parallel formulations of dense matrix multiplication algorithm have been developed. For arbitrarily large number of processors, any of these algorithms or their variants can provide near linear speedup for sufficiently large matrix sizes and none of the algorithms can be clearly claimed to be superior than the others. In this paper we analyze the performance and scalability of a number of parallel formulations of the matrix multiplication algorithm and predict the conditions under which each formulation is better than the others. We present a parallel formulation for hypercube and related architectures that performs better than any of the schemes described in the literature so far for a wide range of matrix sizes and number of processors. The superior performance and the analytical scalability expressions for this algorithm are verified through experiments on the Thinking Machines Corporation&#039;s CM-5  TM y  parallel computer for up to 512 processors. We show that special har...
Parallel Search Algorithms for Robot Motion Planning.
We show how paths for dexterous robots can be generated in a few seconds or less using parallel informed randomized search on multicomputers. The experimental results we present have been obtained for a variety of robots with six or more joints operating in realistic 3D workspaces.  
Efficient Parallel Mappings of a Dynamic Programming Algorithm A Summary of Results.

Performance and Scalability of Preconditioned Conjugate Gradient Methods on the CM%2D5.

On the Efficiency of Parallel Backtracking.
It is known that isolated executions of parallel backtrack search exhibit speedup  anomalies. In this paper we present analytical models and experimental results on the  average case behavior of parallel backtracking. We consider two types of backtrack  search algorithms: (i) simple backtracking (which does not use any heuristic information)  ; (ii) heuristic backtracking (which uses heuristics to order and prune search). We  present analytical models to compare the average number of nodes visited in sequential  and parallel search for each case. For simple backtracking, we show that the average  speedup obtained is (i) linear when distribution of solutions is uniform and (ii) superlinear  when distribution of solutions is non-uniform. For heuristic backtracking, the  average speedup obtained is at least linear (i.e., either linear or superlinear), and the  speedup obtained on a subset of instances (called difficult instances) is superlinear.  We also present experimental results over ...
The Scalability of FFT on Parallel Computers.

Algorithms for Constraint%2DSatisfaction Problems A Survey.
A large variety of problems in Artificial Intelligence and other areas of computer science can be viewed as a special case of the constraint satisfaction problem. Some examples are machine vision, belief maintenance, scheduling, temporal reasoning, graph problems, floor plan design, planning genetic experiments, and the satisfiability problem. A number of different approaches have been developed for solving these problems. Some of them use constraint propagation to simplify the original problem. Others use backtracking to directly search for possible solutions. Some are a combination of these two techniques. This paper presents a brief overview of many of these approaches in a tutorial fashion. 
Performance Properties of Large Scale Parallel Systems.
There are several metrics that characterize the performance of a parallel system, such as, parallel execution time, speedup and efficiency. A number of properties of these metrics have been studied. For example, it is a well known fact that given a parallel architecture and a problem of a fixed size, the speedup of a parallel algorithm does not continue to increase with increasing number of processors. It usually tends to saturate or peak at a certain limit. Thus it may not be useful to employ more than an optimal number of processors for solving a problem on a parallel computer. This optimal number of processors depends on the problem size, the parallel algorithm and the parallel architecture. In this paper we study the impact of parallel processing overheads and the degree of concurrency of a parallel algorithm on the optimal number of processors to be used when the criterion for optimality is minimizing the parallel execution time. We then study a more general criterion of optimalit...
Unstructured Tree Search on SIMD Parallel Computers A Summary of Results.

Scalability Analysis of Partitioning Strategies for Finite Element Graphs A Summary of Results.

Algorithms for Constraint%2DSatisfaction Problems A Survey.
A large variety of problems in Artificial Intelligence and other areas of computer science can be viewed as a special case of the constraint satisfaction problem. Some examples are machine vision, belief maintenance, scheduling, temporal reasoning, graph problems, floor plan design, planning genetic experiments, and the satisfiability problem. A number of different approaches have been developed for solving these problems. Some of them use constraint propagation to simplify the original problem. Others use backtracking to directly search for possible solutions. Some are a combination of these two techniques. This paper presents a brief overview of many of these approaches in a tutorial fashion. 

Depth%2DFirst Versus Best%2DFirst Search.

Analysis of scalability of parallel algorithms and architectures a survey.

Scalability of Parallel Sorting on Mesh Multicomputers.
This paper presents two new parallel algorithms QSP1 and QSP2 based on sequential quicksort for sorting data on a mesh multicomputer, and analyzes their scalability using the isoefficiency metric. We show that QSP2 matches the lower bound on the isoefficiency function for mesh multicomputers. The isoefficiency of QSP1 is also fairly close to optimal. Lang et al. and Schnorr et al. have developed parallel sorting algorithms for the mesh architecture that have either optimal (Schnorr) or close to optimal (Lang) run-time complexity for the one-element-per-processor case. Both QSP1 and QSP2 have worse performance than these algorithms for the one-element-perprocessor case. But QSP1 and QSP2 have better scalability than the scaled-down variants of these algorithms (for the case in which there are more elements than processors). As a result, our new parallel formulations are better than these scaled-down variants in terms of speedup w.r.t the best sequential algorithms. We also present a dif...
A general heuristic bottom%2Dup procedure for searching and%2For graphs.

AND%2DParallel Execution of Logic Programs on a Shared%2DMemory Multiprocessor.

Scalability of Parallel Algorithms for the All%2DPairs Shortest%2DPath Problem.
Abstract This paper uses the isoefficiency metric to analyze the scalability of several parallel algorithms for finding shortest paths between all pairs of nodes in a densely connected graph. Parallel algorithms analyzed in this paper have either been previously presented elsewhere or are small variations of them. Scalability is analyzed with respect to mesh, hypercube and shared-memory architectures. We demonstrate that isoefficiency functions are a compact and useful predictor of performance. In fact, previous comparative predictions of some of the algorithms based on experimental results are shown to be incorrect whereas isoefficiency functions predict correctly. We find the classic tradeoffs of hardware cost vs. time and memory vs. time to be represented here as tradeoffs of hardware cost vs. scalability and memory vs. scalability.

Scalability of Parallel Algorithms for the All%2DPairs Shortest Path Problem A Summary of Results.

Automatic Test Pattern Generation on Multiprocessors A Summary of Results.

Parallel Best%2DFirst Search of State%2DSpace Graphs A Summary of Results.
This paper presents many different parallel formulations of the A*/Branch-and-Bound search algorithm. The parallel formulations primarily differ in the data structures used. Some formulations are suited only for shared-memory architectures, whereas others are suited for distributedmemory architectures as well. These parallel formulations have been implemented to solve the vertex cover problem and the TSP problem on the BBN Butterfly parallel processor. Using appropriate data structures, we are able to obtain fairly linear speedups for as many as 100 processors. We also discovered problem characteristics that make certain formulations more (or less) suitable for some search problems. Since the bestfirst search paradigm of A*/Branch-and-Bound is very commonly used, we expect these parallel formulations to be effective for a variety of problems. Concurrent and distributed priority queues used in these parallel formulations can be used in many parallel algorithms other than parallel A*/bra...
Performance of And%2DParalle Execution of Logic Programs on a Shared%2DMemory Multiprocessor.

Superlinear Speedup in Parallel State%2DSpace Search.

AND%2DParallel Execution of Logic Programs on a Shared Memory Multiprocessor A Summary of Results.

Concurrent Access of Priority Queues.
The heap is an important data structure used as a priority queue in a wide variety of parallel algorithms (e.g., multiprocessor scheduling, branch-and-bound). In these algorithms, contention for the shared heap limits the obtainable speedup. This paper presents an approach to allow concurrent insertions and deletions on the heap in a shared-memory multiprocessor. The scheme also retains the strict priority ordering of the serial-access heap algorithms; i.e., a delete operation returns the best key of all keys that have been inserted or are being inserted at the time delete is started. Our experimental results on the BBN Butterfly parallel processor demonstrate that the use of the concurrent-heap algorithms in parallel branch-and-bound improves its performance substantially. Index Terms: concurrent data structures, priority queues, insertions, deletions, branchand -bound, speedup. 1 Introduction  The heap is an important data structure used as a priority queue in a wide variety of paral...
A Data%2DDependency%2DBased Intelligent Backtracking Scheme for Prolog.

A Parallel Implementation of Iterative%2DDeepening%2DA%2A.
This paper presents a parallel implementation of the Iterative-Deepening A* algorithm on a parallel distributed memorymachine. Two kinds of dynamic load balancing strategies have been studied to overcome the irregular tree search problem. To study the effectiveness of the algorithm, it has been tested to solve a NP-complete problem: the fifteen puzzle. Our experimental results on a cluster of 16 ALPHA processors using PVM show that an efficiency of 97.54% for a speedup of 15.61 could be achieved on a hard problem.
An Intelligent Backtracking Scheme for Prolog.

A Framework for Intelligent Backtracking in Logic Programs.

An Intelligent Backtracking Algorithm for Parallel Execution of Logic Programs.

A Parallel Execution Scheme for Exploiting and Parallelism of Logic Programs.

A General Bottom%2Dup Procedure for Searching And%2FOr Graphs.

Integrating knowledge in problem solving search procedures.

General Branch and Bound%2C and its Relation to A and AO.

The Composite Decision Process A Unifying Formulation for Heuristic Search

A General Branch and Bound Formulation for Understanding and Synthesizing And%2FOr Tree Search Procedures.

A General Paradigm for A.I. Search Procedures.

Branch %26 Bound Formulation for Sequential and Parallel Game Tree Searching Preliminary Results.

The Practical Significance of Distributive Partitioning Sort.

